#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = -1e9;

int main() {
    int course = 4;      // 4门课程
    int totalDays = 7;   // 总共7天

    // 学分收益表，行表示课程，列表示分配的天数，1-based
    vector<vector<int>> credit = {
        {}, // 0行不用
        {0, 4, 4, 5, 8},
        {0, 3, 5, 6, 7},
        {0, 5, 6, 8, 8},
        {0, 2, 4, 7, 8}
    };

    // dp[i][j] = 前 i 门课用 j 天的最大学分
    vector<vector<int>> dp(course + 1, vector<int>(totalDays + 1, INF));
    dp[0][0] = 0;

    // 记录路径
    vector<vector<int>> path(course + 1, vector<int>(totalDays + 1, 0));

    // 状态转移
    for (int i = 1; i <= course; ++i) {
        for (int j = 1; j <= totalDays; ++j) {
            for (int d = 1; d <= 4; ++d) {
                if (j - d >= 0 && dp[i - 1][j - d] != INF) {
                    int gain = dp[i - 1][j - d] + credit[i][d];
                    if (gain > dp[i][j]) {
                        dp[i][j] = gain;
                        path[i][j] = d; // 记录当前课程用了几天
                    }
                }
            }
        }
    }

    // 输出最大总学分
    cout << "最大总学分：" << dp[course][totalDays] << endl;

    // 回溯输出每门课用了多少天
    cout << "每门课分配天数：" << endl;
    int days = totalDays;
    for (int i = course; i >= 1; --i) {
        int used = path[i][days];
        cout << "课程 " << i << " : " << used << " 天" << endl;
        days -= used;
    }

    return 0;
}
